package 简单算法;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: 胡成
 * @Version: 0.0.1V
 * @Date: 2019-05-22
 * @Description: 给出一棵二叉树，返回其节点值的前序遍历。
 * 样例 1:
 * 输入：{1,2,3}
 * 输出：[1,2,3]
 * 解释：
 * 1
 * / \
 * 2   3
 * 它将被序列化为{1,2,3}
 * 前序遍历
 * 样例 2:
 * 输入：{1,#,2,3}
 * 输出：[1,2,3]
 * 解释：
 * 1
 * \
 * 2
 * /
 * 3
 * 它将被序列化为{1,#,2,3}
 * 前序遍历
 * 挑战
 * 你能使用非递归实现么？
 **/
public class 二叉树的前序遍历 {

    public static void main(String[] args) {
        二叉树的前序遍历 s = new 二叉树的前序遍历();

        TreeNode head = new TreeNode(1);
        head.left = new TreeNode(2);
        head.right = new TreeNode(3);
//        System.out.println(s.preorderTraversal2(head));
        System.out.println(s.preorderTraversal(head));
    }

    private List<Integer> deserialize(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        list.addAll(deserialize(root.left));
        list.add(root.val);

        list.addAll(deserialize(root.right));

//        TreeNode leftNode = root.left;
//        TreeNode rightNode = root.right;
//
//        list.add(root.val);
//
//        while (leftNode != null) {
//            list.add(leftNode.val);
//            leftNode = leftNode.left;
//        }
//
//        while (rightNode != null) {
//            list.add(rightNode.val);
//            rightNode = rightNode.left;
//        }

        return list;
    }

    public List<Integer> preorderTraversal(TreeNode root) {
        // write your code here
        if (root == null) {
            return new ArrayList<>();
        }
        return deserialize(root);
    }
}

class TreeNode {
    public int val;
    public TreeNode left, right;

    public TreeNode(int val) {
        this.val = val;
        this.left = this.right = null;
    }
}
